package com.classicInterview;

/**
 * 有一个指定长度的线，问在数组上能覆盖最多多少个点
 *
 * @Author: huangzhigao
 * @Date: 2022/2/12 9:14
 */
public class Code1_CoverMaxPoint {
    /**
     * arr为有序数组,k为长度
     * <p>
     * 解题思路：因为有序，则利用双指针left,right从头部出发，如果right的下一个值-left小于k，则right向右，否则left向右
     *
     * @param arr
     * @param k
     * @return
     */
    public static int MaxCoverLength(int[] arr, int k) {
        int length = 0;
        int left = 0;
        int right = 0;


        while (left < arr.length) {
            while (right < arr.length && arr[right] - arr[left] <= k) {
                right++;
            }
            length = Math.max(right - (left++), length);
        }

        return length;
    }


    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 5};
        System.out.println(MaxCoverLength(arr, 4));
    }
}
